package Solutions

func MaximizeWin(prizePositions []int, k int) int {
	var cache = make([]int, len(prizePositions))
	var maxScore = 0
	var ans = 0
	for ind, val := range prizePositions {
		if val < k {
			maxScore += 1
			cache[ind] = maxScore
			continue
		}
		var ii = binary_search(prizePositions[0:ind+1], val-k)
		var one_score = ind - ii
		if one_score > maxScore {
			maxScore = one_score
		}
		cache[ind] = maxScore
		if ii >= 0 {
			one_score += cache[ii]
		}
		if ans < one_score {
			ans = one_score
		}
	}
	if ans == 0 {
		return cache[len(cache)-1]
	}
	return ans
}

func binary_search(prize []int, target int) int {
	if len(prize) == 0 {
		return -1
	}
	if prize[0] > target {
		return -1
	}
	var left, right = 0, len(prize) - 1
	for left < right {
		var mid = right - (right-left)/2
		if prize[mid] >= target {
			right = mid - 1
		} else {
			left = mid
		}
	}

	if prize[left] >= target {
		return -1

	}
	return left

}
